#include <iostream>
using namespace std;

class Solution {
public:
    int mySqrt(int x) {
    if (x == 0 || x == 1) {
        return x; 
    }  
    int l = 0; 
    int r = x; 
    //已经通过
    while (l <= r) {
        unsigned long long mid = l + ((r - l) >> 1);
        unsigned long long mval = mid * mid;
        if (mval == x) {
            return mid;
        } else if (mval > x) {
            r = mid - 1; 
        } else {
            l = mid + 1; 
        }  
    }  
    return r; 
    }
};
